#region Copyright Notice
// 
// 
//  
//  Copyright (c) 2009-2011 Anindya Chatterjee
//  
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//  
//      http://www.apache.org/licenses/LICENSE-2.0
//  
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
// 
// 
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using AbstractClass.Extensions;
using AbstractClass.Linq;

namespace AbstractClass.Collections.Generic
{
    /// <summary>
    /// Represents a node-based <see cref="BinaryTree&lt;T&gt;"/> data structure which has the following properties:
    /// <para>
    /// <item> The left sub-tree of a node contains only nodes with keys less than the node's key.</item>
    /// <item> The right sub-tree of a node contains only nodes with keys greater than the node's key.</item>
    /// <item> Both the left and right sub-trees must also be binary search trees.</item>
    /// </para>
    /// </summary>
    /// <typeparam name="T">The type of data in the tree.</typeparam>
    [Serializable]
    public class BinarySearchTree<T> : IAlgorithmAwareCollection<T, BinarySearchTree<T>>, IBinaryTree<T>
    {
        private readonly Comparer<T> _comparer = Comparer<T>.Default;

        // ReSharper disable InconsistentNaming
        /// <summary>
        /// Represents the root node of the BinaryTree.
        /// </summary>
        [CLSCompliant(false)]
        protected internal BinaryTreeNode<T> _Root;

        // ReSharper restore InconsistentNaming

        /// <summary>
        /// Initializes a new instance of the <see cref="BinarySearchTree&lt;T&gt;"/> class.
        /// </summary>
        public BinarySearchTree()
        {
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BinarySearchTree&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="collection">The collection of data.</param>
        public BinarySearchTree(IEnumerable<T> collection)
        {
            AddRange(collection);
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="BinarySearchTree&lt;T&gt;"/> class.
        /// </summary>
        /// <param name="comparer">The comparer to sort the data in the tree.</param>
        public BinarySearchTree(Comparer<T> comparer)
        {
            _comparer = comparer;
        }

        /// <summary>
        /// Gets or sets the root node of this instance.
        /// </summary>
        /// <value>The root node.</value>
        public BinaryTreeNode<T> Root
        {
            get { return _Root; }
            protected set { _Root = value; }
        }

        /// <summary>
        /// Gets the comparer associated with this instance.
        /// </summary>
        /// <value>The comparer.</value>
        public IComparer<T> Comparer
        {
            get { return _comparer; }
        }

        /// <summary>
        /// Gets the maximum value in the tree.
        /// </summary>
        /// <value>The maximum value.</value>
        public virtual T Max
        {
            get
            {
                if (Root == null) return default(T);
                BinaryTreeNode<T> current = Root;
                while (current.Right != null)
                {
                    current = current.Right;
                }
                return current.Value;
            }
        }

        /// <summary>
        /// Gets the minimum value in the tree.
        /// </summary>
        /// <value>The minimum value.</value>
        public virtual T Min
        {
            get
            {
                if (Root == null) return default(T);
                BinaryTreeNode<T> current = Root;
                while (current.Left != null)
                {
                    current = current.Left;
                }
                return current.Value;
            }
        }

        #region IAlgorithmAwareCollection<T,BinarySearchTree<T>> Members

        /// <summary>
        ///   Adds an item to the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        /// <param name = "value">The item to add to the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </param>
        public virtual void Add(T value)
        {
            var node = new BinaryTreeNode<T>(value);
            int result;

            BinaryTreeNode<T> current = Root, parent = null;
            while (current != null)
            {
                result = _comparer.Compare(current.Value, node.Value);
                if (result == 0)
                {
                    parent = current;
                    current = current.Left;
                }
                if (result > 0)
                {
                    parent = current;
                    current = current.Left;
                }
                else if (result < 0)
                {
                    parent = current;
                    current = current.Right;
                }
            }

            Count++;
            if (parent == null)
                Root = node;
            else
            {
                result = _comparer.Compare(parent.Value, node.Value);
                if (result > 0)
                    parent.Left = node;
                else
                    parent.Right = node;
            }
        }

        /// <summary>
        ///   Removes all items from the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        public virtual void Clear()
        {
            Root = null;
            Count = 0;
        }

        /// <summary>
        ///   Determines whether the <see cref = "BinarySearchTree&lt;T&gt;" /> contains a specific value.
        /// </summary>
        /// <returns>
        ///   <c>true</c> if <paramref name = "item" /> is found in the <see cref = "BinarySearchTree&lt;T&gt;" />; otherwise, <c>false</c>.
        /// </returns>
        /// <param name = "item">The object to locate in the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </param>
        public virtual bool Contains(T item)
        {
            BinaryTreeNode<T> current = Root;
            while (current != null)
            {
                int result = _comparer.Compare(current.Value, item);
                if (result == 0)
                    return true;
                if (result > 0)
                    current = current.Left;
                else if (result < 0)
                    current = current.Right;
            }

            return false;
        }

        /// <summary>
        /// Copies the elements of the <see cref = "BinarySearchTree&lt;T&gt;" /> to an array of type
        /// <typeparamref name="T"/>, starting at the specified array index.
        /// </summary>
        /// <param name="array">The one-dimensional array of type T that is the destination of
        /// the elements copied from the <see cref = "BinarySearchTree&lt;T&gt;" />. The array must have zero-based indexing.
        ///	 </param>
        /// <param name="index">The zero-based index in array at which copying begins.</param>
        /// <remarks>The nodes are fetched in In-Order fashion.</remarks>
        public void CopyTo(T[] array, int index)
        {
            CopyTo(array, index, BinaryTreeTraversalOrder.InOrder);
        }

        /// <summary>
        ///   Removes the first occurrence of a specific object from the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        /// <param name = "item">The object to remove from the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </param>
        /// <returns>
        ///   <c>true</c> if <paramref name = "item" /> was successfully removed from the <see cref = "BinarySearchTree&lt;T&gt;" />;
        /// 		otherwise, <c>false</c>. This method also returns <c>false</c> if <paramref name = "item" /> is not found in the original
        /// 		<see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </returns>
        public virtual bool Remove(T item)
        {
            if (Root == null)
                return false;

            BinaryTreeNode<T> current = Root, parent = null;
            int result = _comparer.Compare(current.Value, item);
            while (result != 0)
            {
                if (result > 0)
                {
                    parent = current;
                    current = current.Left;
                }
                else if (result < 0)
                {
                    parent = current;
                    current = current.Right;
                }

                if (current == null)
                    return false;
                result = _comparer.Compare(current.Value, item);
            }

            Count--;

            if (current.Right == null)
            {
                if (parent == null)
                    Root = current.Left;
                else
                {
                    result = _comparer.Compare(parent.Value, current.Value);
                    if (result > 0)
                        parent.Left = current.Left;
                    else if (result < 0)
                        parent.Right = current.Left;
                }
            }
            else if (current.Right.Left == null)
            {
                current.Right.Left = current.Left;

                if (parent == null)
                    Root = current.Right;
                else
                {
                    result = _comparer.Compare(parent.Value, current.Value);
                    if (result > 0)
                        parent.Left = current.Right;
                    else if (result < 0)
                        parent.Right = current.Right;
                }
            }
            else
            {
                BinaryTreeNode<T> leftmost = current.Right.Left, lmParent = current.Right;
                while (leftmost.Left != null)
                {
                    lmParent = leftmost;
                    leftmost = leftmost.Left;
                }

                lmParent.Left = leftmost.Right;

                leftmost.Left = current.Left;
                leftmost.Right = current.Right;

                if (parent == null)
                    Root = leftmost;
                else
                {
                    result = _comparer.Compare(parent.Value, current.Value);
                    if (result > 0)
                        parent.Left = leftmost;
                    else if (result < 0)
                        parent.Right = leftmost;
                }
            }

            current.Left = current.Right = null;

            return true;
        }

        /// <summary>
        ///   Gets the number of elements contained in the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        /// <returns>
        ///   The number of elements contained in the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </returns>
        public int Count { get; protected internal set; }

        /// <summary>
        ///   Gets a value indicating whether the <see cref = "BinarySearchTree&lt;T&gt;" /> is read-only.
        /// </summary>
        /// <returns>
        ///   true if the <see cref = "BinarySearchTree&lt;T&gt;" /> is read-only; otherwise, false.
        /// </returns>
        public bool IsReadOnly
        {
            get { return false; }
        }

        #endregion

        #region IBinaryTree<T> Members

        void IBinaryTree<T>.OnNodeChange(BinaryTreeNode<T> node)
        {
        }

        #endregion

        /// <summary>
        /// Removes all the elements filtered by the specified predicate from the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        /// <param name="match">The predicate to filter out the elements from the <see cref = "BinarySearchTree&lt;T&gt;" />.</param>
        /// <returns>The number of elements remove from the <see cref = "BinarySearchTree&lt;T&gt;" />.</returns>
        public int RemoveWhere(Predicate<T> match)
        {
            match.ThrowIfNull("match");

            var matches = new List<T>(Count);
            if (Root != null)
                Root.ToEnumerable(BinaryTreeTraversalOrder.BreadthFirst).Process(n =>
                                                                                     {
                                                                                         if (match(n.Value))
                                                                                         {
                                                                                             matches.Add(n.Value);
                                                                                         }
                                                                                     });

            int num = 0;
            for (int i = matches.Count - 1; i >= 0; i--)
            {
                if (Remove(matches[i]))
                {
                    num++;
                }
            }
            return num;
        }

        /// <summary>
        /// Adds the elements of the specified collection into the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        /// <param name="items">The collection of items to add to the <see cref = "BinarySearchTree&lt;T&gt;" />.</param>
        public void AddRange(IEnumerable<T> items)
        {
            foreach (T item in items)
            {
                Add(item);
            }
        }

        /// <summary>
        /// Copies the elements of the <see cref = "BinarySearchTree&lt;T&gt;" /> to an array of type
        /// T, starting at the specified array index in a order specified by <seealso cref="BinaryTreeTraversalOrder"/>.
        /// </summary>
        /// <param name="array">The one-dimensional array of type T that is the destination of
        /// the elements copied from the <see cref = "BinarySearchTree&lt;T&gt;" />. The array must have zero-based indexing.
        ///	 </param>
        /// <param name="index">The zero-based index in array at which copying begins.</param>
        /// <param name="traversalOrder">Type of the tree traversal to the retrieve the data from it.</param>
        public void CopyTo(T[] array, int index, BinaryTreeTraversalOrder traversalOrder)
        {
            Root.ToEnumerable(traversalOrder).Select(x => x.Value).ToArray().CopyTo(array, index);
        }

        /// <summary>
        /// Finds the specified value from <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        /// <param name="value">The value to find from the <see cref = "BinarySearchTree&lt;T&gt;" />.</param>
        /// <returns>
        /// A <see cref="BinaryTreeNode&lt;T&gt;"/> object is search is successful; otherwise, <c>null</c>.
        /// </returns>
        public virtual BinaryTreeNode<T> Find(T value)
        {
            BinaryTreeNode<T> current = Root;
            while (current != null)
            {
                int result = _comparer.Compare(current.Value, value);
                if (result == 0)
                    return current;
                if (result > 0)
                    current = current.Left;
                else if (result < 0)
                    current = current.Right;
            }

            return null;
        }

        /// <summary>
        /// Rebuilds the depths of each nodes in the <see cref = "BinarySearchTree&lt;T&gt;" /> after alteration.
        /// </summary>
        public void RebuildNodeDepth()
        {
            var queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(Root);

            while (0 < queue.Count)
            {
                BinaryTreeNode<T> node = queue.Dequeue();
                if (node != null)
                {
                    if (node.Left != null) queue.Enqueue(node.Left);
                    if (node.Right != null) queue.Enqueue(node.Right);
                }

                if (node != null) node.Depth = node.IsRoot() ? 0 : node.Parent.Depth + 1;
            }
        }

        #region Implementation of IAlgorithmAware<out BinarySearchTree<T>>

        /// <summary>
        /// Executes the <paramref name="algorithm"/> on the <see cref = "BinarySearchTree&lt;T&gt;" />.
        /// </summary>
        /// <typeparam name="TResult">The type of the result.</typeparam>
        /// <param name="algorithm">The algorithm to run on the <see cref = "BinarySearchTree&lt;T&gt;" />.</param>
        /// <returns>The result of execution of the <paramref name="algorithm"/> on the <see cref = "BinarySearchTree&lt;T&gt;" />.</returns>
        public TResult ExecuteAlgorithm<TResult>(IAlgorithm<BinarySearchTree<T>, TResult> algorithm)
        {
            algorithm.ThrowIfNull("algorithm");
            return algorithm.Run(this);
        }

        #endregion

        #region Implementation of IEnumerable

        /// <summary>
        ///   Returns an enumerator that iterates through the collection.
        /// </summary>
        /// <returns>
        ///   A <see cref = "IEnumerator&lt;T&gt;" /> that can be used to iterate through the collection.
        /// </returns>
        public IEnumerator<T> GetEnumerator()
        {
            return Root.ToEnumerable(BinaryTreeTraversalOrder.InOrder).Select(x => x.Value).GetEnumerator();
        }

        /// <summary>
        ///   Returns an enumerator that iterates through a collection.
        /// </summary>
        /// <returns>
        ///   An <see cref = "IEnumerator" /> object that can be used to iterate through the collection.
        /// </returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion
    }
}